package _18_剑指OfferII;

import java.util.Arrays;

// 由于直方图的每个矩形的宽度为1, 所以寻求最大面积其实可以看做左边第一个比其小的
// 然后计算左右两边面积，谁大谁小
public class _039_剑指OfferII直方图最大矩形面积 {

    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        int[] rightMin = new int[len];
        Arrays.fill(rightMin, -1);
        for (int i = len - 2; i >= 0; --i) {
            int position = i + 1;
            while (heights[position] >= heights[i]) {
                if (rightMin[position] == -1) {
                    position = -1;
                    break;
                } else {
                    position = rightMin[position];
                }
            }
            rightMin[i] = position;
        }
        int[] leftMin = new int[len];
        Arrays.fill(leftMin, -1);
        for (int i = 1; i < len; ++i) {
            int position = i - 1;
            while (heights[position] >= heights[i]) {
                if (leftMin[position] == -1) {
                    position = -1;
                    break;
                } else {
                    position = leftMin[position];
                }
            }
            leftMin[i] = position;
        }

        // 计算最大面积
        int area = 0;
        for (int i = 0; i < len; ++i) {
            int leftWidth = leftMin[i] == -1? i + 1: i - leftMin[i];
            int rightWidth = rightMin[i] == -1? len - i: rightMin[i] - i;
            area = Math.max(area, (leftWidth + rightWidth - 1) * heights[i]);
        }
        return area;
    }

}
